<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>排序算法</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	/*
	排序算法有很多：冒泡排序、选择排序、插入排序、归并排序、计数排序（counting sort）、基数排序（radix sort）、希尔排序、堆排序、桶排序
	
	学习目标：
	简单排序：冒泡排序-选择排序-插入排序
	高级排序：希尔排序 - 快速排序
	
	冒泡排序：
		对末尾排序的各元素从头到尾依次比较相邻的两个元素大小关系
		如果左边的队员高，则两队员交换位置
		向右移动一个位置，比较下面两个队员
		 当走到最右端时，最高的队员一定被放在了最右边
		 依次类推
		 
	
	选择排序改进了冒泡排序：
		将交换的次数由O（n²） 减少到O（N）
		但是比较的次数依然是O（n²）
		 
	选择排序：
		选定第一个索引位置，然后和后面元素依次比较
		如果后面的队员，小于第一个索引位置的队员，则交换位置
		经过一轮的比较后，可以确定第一个位置是最小的
		然后使用同样的方法把剩下的元素逐个比较即可
	
	插入排序的效率：
		插入排序的比较次数：N*（N-1）/ 4
		复制次数：N*（N-1）/ 4
		
	插入排序：
		插入排序是学习其他高级排序的基础，比如希尔排序、快速排序
		插入排序的思想：
			局部有序：
	
	
	对于基本有序的情况：
		对于已经有序或基本有序的数据来说，插入排序要好很多
		当数据有序的时候，while循环的条件总是为加，所以它变成了外层循环中的一个简单语句，指向N-1次
		在这种情况下，算法运行至需要N（N）的时间，效率相对来说会更高
		我们的比较次数是选择排序的一半，所以这个算法的效率是高于选择排序的
		
		
	希尔排序：（原稿增量、Hibbard增量序列、Sedgewick增量序列）
		希尔排序是插入排序的一种高效的改进版，并且效率比插入排序要更快
		
		
	快速排序：几乎可以说是目前所有排序算法中，最快的一种排序算法
		快速排序最重要的思想是分而治之。
		选择枢纽：中位数
	*/

	/*
   
	*/

	// 列表类
	function ArrayList() {
		// 属性
		this.array = []
		// 方法
		// 将数据可以插入到数组的方法
		ArrayList.prototype.insert = function(item) {
			this.array.push(item)
		}
		// toString
		ArrayList.prototype.toString = function() {
			return this.array.join('-')
		}
		// 交换两个位置的数据
		ArrayList.prototype.swap = function(m, n) {
			var temp = this.array[m]
			this.array[m] = this.array[n]
			this.array[n] = temp
		}
		// 实现排序
		// 冒泡排序
		ArrayList.prototype.bubbleSort = function() {

			// 1.获取数组的长度
			var length = this.array.length

			for (var j = length - 1; j >= 0; j--) {
				// 第一次进来：i=0，比较0和1位置的两个数据，如果0位置大于1位置的数据
				// 最后依次进来：i=length-2,比较length - 2 和length -1 的两个数据
				for (var i = 0; i < j; i++) {
					if (this.array[i] > this.array[i + 1]) {
						this.swap(i, i + 1)
					}
				}
			}

		}
		// 选择排序
		ArrayList.prototype.selectSort = function() {

			//获取length
			var length = this.array.length
			for (j = 0; j < length - 1; j++) {
				var min = j;
				for (var i = min + 1; i < length; i++) {
					if (this.array[min] > this.array[i]) {
						min = i
					}
				}
				this.swap(min, j)
			}
		}
		// 插入排序
		ArrayList.prototype.insertionSort = function() {
			// 1.获取数组的长度
			var length = this.array.length;

			// 2.外层循环：从第一个位置开始获取数据，向前面局部有序进行插入
			for (var i = 1; i < length; i++) {
				// 3.内层循环，获取i位置的元素，和前面的数据一次进行比较
				var temp = this.array[i]
				console.log("temp",temp)
				var j = i;
				while (this.array[j - 1] > temp && j > 0) {
					this.array[j] = this.array[j - 1]
					j--
				}
				// 4.将j位置的数据，放置temp就可以
				this.array[j] = temp
			}
		}
		// 希尔排序 （原稿增量）
		ArrayList.prototype.shell = function() {
			// 1.获取数组的长度
			var length = this.array.length
			// 2.初始化的增量(gap ->间隔)
			var gap = Math.floor(length / 2)

			// 3.while循环(gap不断的减小)
			while (gap >= 1) {
				// 4.以gap作为间隔，进行分组，对分组进行插入排序
				for (var i = gap; i < length; i++) {
					var temp = this.array[i]
					var j = i
					while (this.array[j - gap] > temp && j > gap - 1) {
						this.array[j] = this.array[j - gap]
						j -= gap
					}
					// 5.将j位置的元素赋值temp
					this.array[j] = temp
				}
				gap=Math.floor(gap/2)

			}
		}
		// 快速排序
		ArrayList.prototype.quickSort = function(){
			this.quick(0,this.array.length-1)
		}
		ArrayList.prototype.quick = function(left,right){
			// 1.结束条件
			if(left >= right) return
			// 2.枢纽
			var pivot = this.median(left,right)
			// 3.定义变量，用于记录当前找到的位置
			var i= left
			var j = right -1
			// 4.开始进行交换
			while(i < j){
				while(this.array[i] < pivot && i < j){i++}
				while(this.array[j] >= pivot && i < j){j--}
				if(i < j){this.swap(i,j)}else{break}
			}
			// 6.将枢纽放在正确的位置，i的位置
			this.swap(i,right-1)
			// 7.分而治之
			this.quick(left,i-1)
			this.quick(i+1,right)
		}
		// 选择枢纽：中位数
		ArrayList.prototype.median = function(left,right){
			// 1.中间的数
			var center = Math.floor((left+right)/2)
			// 2.判断大小，并且进行交换
			if(this.array[left] > this.array[center]){this.swap(left,center)}
			if(this.array[center] > this.array[right]){this.swap(center,right)}
			if(this.array[left] > this.array[right]){this.swap(left,right)}
			// 3.将换到right-1的位置
			this.swap(center,right-1)
			return this.array[right-1]
		}
	}

	// 测试
	var list = new ArrayList()

	// 插入元素
	list.insert(66)
	list.insert(88)
	list.insert(12)
	list.insert(87)
	list.insert(100)
	list.insert(5)
	list.insert(566)
	list.insert(23)
	list.insertionSort()
	console.log(list.toString())
	// list.bubbleSort()
	// console.log(list.toString())
	// 希尔排序
	// list.shell()
    
	// 快速排序
	
	// list.quickSort()
	// console.log(list.toString())
	
</script>
